Search for: All records

Abstract Ann-vertex graph is calledC-Ramseyif it has no clique or independent set of size$$C\log _2 n$$(i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of aC-Ramsey graph. This brings together two ongoing lines of research: the study of ‘random-like’ properties of Ramsey graphs and the study of small-ball probability for low-degree polynomials of independent random variables. The proof proceeds via an ‘additive structure’ dichotomy on the degree sequence and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics and low-rank approximation. In particular, a key ingredient is a new sharpened version of the quadratic Carbery–Wright theorem on small-ball probability for polynomials of Gaussians, which we believe is of independent interest. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős reiterated in several of his open problem collections and for which he offered one of his notorious monetary prizes. 

Abstract Bollobás and Riordan, in their paper ‘Metrics for sparse graphs’, proposed a number of provocative conjectures extending central results of quasirandom graphs and graph limits to sparse graphs. We refute these conjectures by exhibiting a sequence of graphs with convergent normalized subgraph densities (and pseudorandom C 4 -counts), but with no limit expressible as a kernel. 

Abstract Does every $$n$$-vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are $$O(1/\sqrt{n})$$? While the answer is yes for abelian groups, we show that it is no in general. On the other hand, we show that every $$n$$-vertex Cayley graph (and more generally, vertex-transitive graph) has an orthonormal basis whose coordinates are all $$O(\sqrt{\log n / n})$$, and that this bound is nearly best possible. Our investigation is motivated by a question of Assaf Naor, who proved that random abelian Cayley graphs are small-set expanders, extending a classic result of Alon–Roichman. His proof relies on the existence of a bounded eigenbasis for abelian Cayley graphs, which we now know cannot hold for general groups. On the other hand, we navigate around this obstruction and extend Naor’s result to nonabelian groups.